package com.xc.dictionary;

import java.util.ArrayList;
import java.util.List;

public class WordSuggester {
    private TrieNode root;

    public WordSuggester() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.containsKey(ch)) {
                node.put(ch, new TrieNode());
            }
            node = node.get(ch);
        }
        node.setEndOfWord();
    }

    public List<String> suggest(String prefix) {
        List<String> suggestions = new ArrayList<>();
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            node = node.get(ch);
            if (node == null) {
                return suggestions;
            }
        }
        collectWords(node, new StringBuilder(prefix), suggestions);
        return suggestions;
    }

    private void collectWords(TrieNode node, StringBuilder path, List<String> suggestions) {
        if (node.isEndOfWord()) {
            suggestions.add(path.toString());
        }
        for (char ch = 'a'; ch <= 'z'; ch++) {
            if (node.containsKey(ch)) {
                path.append(ch);
                collectWords(node.get(ch), path, suggestions);
                path.deleteCharAt(path.length() - 1);
            }
        }
    }

    public static void main(String[] args) {
        WordSuggester suggester = new WordSuggester();
        suggester.insert("apple");
        suggester.insert("app");
        suggester.insert("banana");
        suggester.insert("orange");
        suggester.insert("application");
        suggester.insert("apply");
        List<String> suggestions = suggester.suggest("ap");
        System.out.println("Suggestions: " + suggestions);
    }
}
